package com.mgq.algorithm.twotree;

/**
 * 平衡二叉树
 * 定义:
 * 对于一个子树,左子树和右子树的高度差不能超过1
 */
public class AVL {

    /**
     * 判断一个树是否为平衡二叉树
     * DP
     * 找共同点:
     * 1.左子树是平衡二叉树
     * 2.右子树是平衡二叉树
     * 3.左子树和左子树的高度差不能超过1
     *
     * 先分析可能性
     * 可能性: 3个条件必须满足
     *
     * 整理条件
     * 整理: 左子树和右子树需要给出什么信息,才能判断
     *
     * 需要左子树提供高度,是否是平衡的.
     * 需要右子树提供高度,是否是平衡的.
     *
     * 条件一致:
     * 使用递归
     *
     *
     * @param root
     * @return
     */
    public boolean isAVL(TreeNode root) {
       return process(root).isAVL;
    }

    /**
     * 生成process函数
     * @return
     */
    public ReturnType process(TreeNode root){

        //处理base case (递归的终止条件)
        if (root == null) {
            return new ReturnType(0, true);
        }
        //左边返回值
        ReturnType leftReturn = process(root.left);
        //右边返回值
        ReturnType rightReturn = process(root.right);

        //构造自己的返回条件
        //首先是高度 height
        //其次是否是平衡二叉树
        int height = Math.max(leftReturn.height, rightReturn.height)+1;
        //自己的高度等于左树和右树的最大高度+1
        //是否是平衡二叉树 左树和右树都是平衡树,且左树和右树的高度差不超过1
        boolean isAVL= leftReturn.isAVL && rightReturn.isAVL
                && Math.abs(leftReturn.height- rightReturn.height) <=1;
        return new ReturnType(height, isAVL);
    }

    /**
     * 需要返回的值
     */
    class ReturnType{
        int height;
        boolean isAVL;

        public ReturnType(int height, boolean isAVL) {
            this.height = height;
            this.isAVL = isAVL;
        }
    }
}
